/*
 * @Author: szx
 * @Date: 2022-06-14 11:10:45
 * @LastEditTime: 2022-06-14 11:32:56
 * @Description:
 * @FilePath: \leetcode\面试题\17\08\08.js
 */
/**
 * @param {number[]} height
 * @param {number[]} weight
 * @return {number}
 */
/**
 * @param {number[]} height
 * @param {number[]} weight
 * @return {number}
 */
var bestSeqAtIndex = function (height, weight) {
    const data = [];
    for (let i = 0; i < height.length; i++) {
        data.push({
            height: height[i],
            weight: weight[i]
        });
    }
    // 身高从低到高，重量从大到小
    data.sort((a, b) => {
        if (a.height === b.height) return b.weight - a.weight;
        return a.height - b.height;
    });
    // 利用二分法获取weight的最长子串的值就是结果
    let res = 0;
    const dp = [];
    for (let index in data) {
        index = Number(index);
        let w = data[index].weight;
        let i = 0;
        let j = res;
        while (i < j) {
            const m = parseInt((i + j) / 2);
            if (dp[m] < w) {
                i = m + 1;
            } else {
                j = m;
            }
        }
        dp[i] = w;
        if (j === res) res++;
    }
    return res;
};
var bestSeqAtIndex = function (height, weight) {
    const data = [];
    for (let i = 0; i < height.length; i++) {
        data.push({
            height: height[i],
            weight: weight[i]
        });
    }
    const nums = data.map((v) => v.weight);
    return lengthOfLIS(nums);
};
var lengthOfLIS = function (nums) {
    const n = nums.length;
    const dp = new Array(n).fill(1);
    let max = 0;
    for (let i = 0; i < n; i++) {
        for (let j = i; j >= 0; j--) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[j] + 1, dp[i]);
            }
        }
        max = Math.max(dp[i], max);
    }
    return max;
};
